#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct term
{
    int expn;          // 指数
    float cofe;        // 系数
    struct term *next; // 指向下一个

} term;

void init_term(term *node) // 初始化
{
    node->expn = 0;
    node->cofe = 0;
    node->next = NULL;
}
void CreatPolyn(term *head, float coef, int expn) // 输入系数coef和指数expn,构造这一项
{
    term *p = (term *)malloc(sizeof(term)); // 向前探索
    term *q = (term *)malloc(sizeof(term)); // 紧随在p后面指向p
    init_term(p);
    init_term(q);
    if (head->next != NULL) // 如果链表不为空
    {
        p = head->next; // p指向第一个节点
        q = head;       // 紧随p后
    }
    else // 链表为空
    {
        term *node = (term *)malloc(sizeof(term)); // 新建一个term
        init_term(node);                           // 初始化
        node->expn = expn;                         // 赋值
        node->cofe = coef;                         // 赋值
        head->next = node;                         // 因为只有头节点,所以直接接到头节点就可以
        return;                                    // 结束函数
    }
    while (p != NULL) // 含有多个节点,寻找合适的插入位置
    {
        if (p->expn < expn)
        {
            p = p->next; // 往后走
            q = q->next; // 往后走
        }
        else if (p->expn == expn) // 项数相等的项,直接加法
        {
            // 指数(expn)不变
            p->cofe += coef; // 系数相加
            // 看看相加之后系数是不是等于0
            if (p->cofe == 0) // 如果系数等于0
            {
                if (p->next != NULL) // p不是最后一个节点
                {
                    q->next = p->next; // 在链表中取出,最后释放p
                }
                else // p在最后
                {
                    q->next = NULL; // 调整q指向
                }
                free(p);
                return; // 结束函数,防止死循环
            }
            return; // 如果不等于0就结束函数,防止死循环
        }
        else // 当前指数大于要插入的指数
        {
            // 在p前面插入(在p与q之间插入)
            term *node = (term *)malloc(sizeof(term)); // 新建一个term
            init_term(node);                           // 初始化
            node->expn = expn;                         // 赋值
            node->cofe = coef;                         // 赋值
            q->next = node;                            // 链接前面的的q
            node->next = p;                            // 链接后面的p
            return;                                    // 结束函数
        }
    }
    // 出来了,代表p可能到Null了,即最后一项的指数小于插入项的指数
    if (p == NULL)
    {
        term *node = (term *)malloc(sizeof(term)); // 新建一个term
        init_term(node);                           // 初始化
        node->expn = expn;                         // 赋值
        node->cofe = coef;                         // 赋值
        q->next = node;                            // 尾插新的一项
        return;
    }
    return;
}

void PrintPolyn(term *head) // 打印多项式
{
    while (head->next != NULL)
    {
        head = head->next;
        if (head->next != NULL)
        {
            printf("(%.1f)X^%d+", head->cofe, head->expn);
        }
        else
        {
            printf("(%.1f)X^%d", head->cofe, head->expn);
        }
    }
    printf("\n");
}

int PolynLength(term *head)
{
    int length = 0;
    while (head->next != NULL)
    {
        head = head->next;
        length++;
    }
    return length;
}

void Delete_Ployn(term *head)
{
    while (head->next != NULL)
    {
        term *p = head->next;
        head->next = p->next;
        free(p);
    }
    printf("清空多项式完成!\n");
}

void AddPolyn(term *head_a, term *head_b) // 两个多项式相加
{
    // 执行两个多项式加法,其中head_a和head_b是两个头指针。
    // 我的习惯是最大限度不改变头指针指向
    term *pa = NULL, *pb = NULL; // pa与pb是遍历两条链用的;
    term *new_a = head_a;        // new_a是重新构造a链的指针
    if (head_a->next != NULL)    // 确保不是空多项式相加
    {
        pa = head_a->next;
    }
    if (head_b->next != NULL) // 确保不是空多项式相加
    {
        pb = head_b->next;
    }
    while (pa && pb) // 两条链只要有一个没到头就继续往下走
    {
        if (pa->expn < pb->expn) // a的这一项的指数小于b的这一项的指数
        {
            new_a->next = pa;    // 在a链上插入
            pa = pa->next;       // pa向后走
            new_a = new_a->next; // new_a往后走
        }
        else if (pa->expn > pb->expn) // a的这一项的指数大于b的这一项的指数
        {
            // 插入b的这一项
            new_a->next = pb;
            pb = pb->next;
            new_a = new_a->next;
        }
        else // 两条链指数相等
        {
            // 执行相加,删除b的这一项,删除系数0的项
            pa->cofe += pb->cofe; // 系数相加
            if (pa->cofe == 0)    // 系数等于0
            {
                term *temp = pa; // 暂存这个空间
                pa = pa->next;   // pa往后走
                pb = pb->next;   // pb往后走
                free(temp);      // 释放无用空间  //前一个指向未设置NULL
            }
            else // 系数不为0
            {
                new_a->next = pa;    // 把这一项放入head_a
                pa = pa->next;       // pa后走
                new_a = new_a->next; // new_a后走
                term *temp = pb;
                pb = pb->next; // pb后走
                free(temp);    // 释放无用节点
            }
        }
    }

    if (pa != NULL) // pb提前结束
    {
        new_a->next = pa;
    }
    else if (pb != NULL) // pa提前结束(可能同时结束)
    {
        new_a->next = pb;
    }
    else // 同时退出
    {
        new_a->next = NULL;
    }
    head_b->next = NULL;
    return;
}

void SubPolyn(term *pa, term *pb) // 两个多项式相减
{
    // 不知道减法与加法有什么区别,就不写了
}

void MulPolyn(term *head_a, term *head_b) // 两个多项式相乘
{
    // 实现多项式乘法
    /*
    int expn;          // 指数
    float cofe;        // 系数
    */
    term *pa = NULL, *pb = NULL; // pa与pb是遍历两条链用的;
    // 想不出来如何不新建一个链表就实现乘法操作的办法
    term *head_c = (term *)malloc(sizeof(term)); // 存放乘法结果
    init_term(head_c);

    if (head_a->next != NULL) // 确保不是空多项式相加
    {
        pa = head_a->next;
    }
    if (head_b->next != NULL) // 确保不是空多项式相加
    {
        pb = head_b->next;
    }
    while (pa) // 对pa的每一项进行操作(不需要对a也使用temp,因为a只用一次)
    {
        term *temp = pb; // 这个temp可以避免一次循环后pb边为空进而无法继续循环的情况
        while (temp)     // 使用pa的每一项乘pb的每一项
        {
            float this_cofe = pa->cofe * temp->cofe;
            int this_expn = pa->expn + temp->expn;
            CreatPolyn(head_c, this_cofe, this_expn);
            temp = temp->next;
        }
        pa = pa->next; // 下一项
    }
    // PrintPolyn(head_c);
    printf("释放函数里无用空间:\n");
    Delete_Ployn(head_a);
    Delete_Ployn(head_b);
    head_a->next = head_c->next;  //不能直接赋值,因为是引用,所以应该写指向
}

int main()
{
    // 构造有头节点的多项式链表
    term *head_a = (term *)malloc(sizeof(term));
    init_term(head_a); // 初始化头节点
    // 构造一个多项式
    for (int i = 0; i < 7; i += 2)
    {
        float coef = i + 3;             // 随便构造的系数
        int expn = i * 2;               // 随便构造的指数
        CreatPolyn(head_a, coef, expn); // cofe是系数,expn是指数
    }
    printf("多项式a:");
    PrintPolyn(head_a);
    printf("多项式项数为:%d\n", PolynLength(head_a));
    // 验证相同指数相加是否正确
    CreatPolyn(head_a, -5, 4); // cofe是系数,expn是指数,对x的5次方系数-2

    // 输出看一下
    printf("多项式a:");
    PrintPolyn(head_a);

    // PolynLenth  返回多项式中的项数
    printf("多项式a的项数为:%d\n", PolynLength(head_a));

    // 构造多项式b
    term *head_b = (term *)malloc(sizeof(term));
    init_term(head_b); // 初始化头节点
    for (int i = 0; i < 7; i += 2)
    {
        float coef = i + 1;             // 随便构造的系数
        int expn = i;                   // 随便构造的指数
        CreatPolyn(head_b, coef, expn); // cofe是系数,expn是指数
    }
    CreatPolyn(head_b, -9, 12); // 测试插入
    CreatPolyn(head_b, 2, 13);  // 测试插入
    printf("多项式b:");
    PrintPolyn(head_b);
    printf("多项式b的项数为:%d\n", PolynLength(head_b));

    // 函数AddPolyn()两个多项式相加
    AddPolyn(head_a, head_b); // 几点修改长度！！！
    printf("执行加法后的多项式a:");
    PrintPolyn(head_a);
    printf("执行加法后的多项式a的项数为:%d\n", PolynLength(head_a));

    // 函数SubPolyn()两个多项式相减
    // 不知道减法与加法有什么区别,就不写了

    // 函数MulPolyn()两个多项式相乘
    for (int i = 0; i < 7; i += 2)
    {
        float coef = i + 1;             // 随便构造的系数
        int expn = i;                   // 随便构造的指数
        CreatPolyn(head_b, coef, expn); // cofe是系数,expn是指数
    }
    printf("多项式b:");
    PrintPolyn(head_b);
    // 清空a方便计算
    printf("清空多项式a方便验证正确性,清空多项式head_a:");
    Delete_Ployn(head_a);
    CreatPolyn(head_a, 1, 0); // 加上两个短的项
    CreatPolyn(head_a, 1, 2);
    printf("新的多项式a:");
    PrintPolyn(head_a); // a=1+x^2

    MulPolyn(head_a, head_b);
    printf("执行乘法后的多项式a:");
    PrintPolyn(head_a);
    // PrintPolyn(head_a);
    // Delete_Ployn 删除整个多项式
    printf("清空多项式a:");
    Delete_Ployn(head_a);
    PrintPolyn(head_a);
    return 0;
}